package dk.itu.KrakMap;

import java.util.*;

/**
 * KrakQuadTree data structure, made specificly for the KrakNode objects, to provide
 * a more efficient mean of comparing the points, without fx. auto-boxing.
 *
 * The KrakQuadTree stores all added nodes in 2D structure, for faster queries for
 * ranges of data, eg. the 2DQuery method.
 *
 * Be aware that many recursive calls are made, and to avoid stack-overflow
 * you should avoid using to low nodeCapacities. 5 is a minimum, but min 20 is
 * recomended for larger datasets.
 *
 * @author ITU-KF04-2011, Group 11
 */
public class KrakQuadTree {

    private KrakQuadTreeNode root;
    private final int nodeCapacity;

    // helper node data type
    private class KrakQuadTreeNode {

        Viewport viewport;
        KrakEdge[] nodes;
        int count = 0;
        KrakQuadTreeNode NW, NE, SE, SW;   // four subtrees

        public KrakQuadTreeNode(Viewport viewport) {
            this.viewport = viewport;
        }

        public void insert(KrakEdge data) {
            //Node is a leaf and is not initialized yet; Initialize and insert data.
            if (nodes == null && count == 0) {
                nodes = new KrakEdge[nodeCapacity];
                nodes[count++] = data;
                //Node is not a leaf; distribute data.
            } else if (nodes == null) {
                distribute(data);
                //Node is a leaf and still has capacity; insert data.
            } else if (count < nodeCapacity) {
                nodes[count++] = data;
                //Node is a leaf, but is full. Distribute it's data.
            } else {
                distribute(nodes);
                distribute(data);
                nodes = null;
            }
        }

        private void distribute(KrakEdge[] data) {
            //Initialize sub-trees
            NW = new KrakQuadTreeNode(
                    new Viewport(
                    viewport.getDownLeft().getX(),
                    viewport.getCenter().getY(),
                    viewport.getCenter().getX(),
                    viewport.getUpRight().getY()));
            NE = new KrakQuadTreeNode(
                    new Viewport(
                    viewport.getCenter(),
                    viewport.getUpRight()));
            SE = new KrakQuadTreeNode(
                    new Viewport(
                    viewport.getCenter().getX(),
                    viewport.getDownLeft().getY(),
                    viewport.getUpRight().getX(),
                    viewport.getCenter().getY()));
            SW = new KrakQuadTreeNode(
                    new Viewport(
                    viewport.getDownLeft(),
                    viewport.getCenter()));
            for (KrakEdge e : data) {
                distribute(e);
            }
        }

        private void distribute(KrakEdge data) {
            MapPoint m1 = data.v1.getMapPoint();
            MapPoint m2 = data.v2.getMapPoint();
            if (NW.viewport.contains(m1) || NW.viewport.contains(m2)) {
                NW.insert(data);
            }
            if (NE.viewport.contains(m1) || NE.viewport.contains(m2)) {
                NE.insert(data);
            }
            if (SE.viewport.contains(m1) || SE.viewport.contains(m2)) {
                SE.insert(data);
            }
            if (SW.viewport.contains(m1) || SW.viewport.contains(m2)) {
                SW.insert(data);
            }
        }
    }

    /**
     * Construct a new KrakQuadTree
     *
     * @param maxViewport The maximum viewport of the KrakQuadTree.
     * @param nodeCapacity Max number of nodes in leaf before it splits
     */
    public KrakQuadTree(Viewport maxViewport, int nodeCapacity) {
        if (nodeCapacity < 5) {
            throw new IllegalArgumentException("Minimum nodeCapacity is 5");
        }
        root = new KrakQuadTreeNode(maxViewport);
        this.nodeCapacity = nodeCapacity;
    }

    /**
     * Insert a node into the QuadTree. (NOTE: The node must be contained within
     * the maximum viewport (specified on initialization).
     * 
     * @param edge The edge to be inserted.
     */
    public void insert(KrakEdge edge) {
        root.insert(edge);
    }

    /**
     * Get all nodes, within the specified Viewport. The search rather fast,
     * for smaller subsets, as it can easily filter out unwanted results, due
     * to the QuadTree data structure.
     *
     * @param rect The Viewport in which to find nodes.
     * @return A list of notes that are on the specified viewport.
     */
    public HashSet<KrakEdge> query2D(Viewport rect) {
        HashSet<KrakEdge> result = new HashSet<KrakEdge>();
        query2D(root, rect, result);
        return result;
    }

    /**
     * Recursive method for making 2D queries.
     *
     * @param n The node to search in.
     * @param rect The Viewport searched for
     * @param result The ArrayList, where to add all matched nodes.
     */
    private void query2D(KrakQuadTreeNode n, Viewport rect, HashSet<KrakEdge> result) {

        if (n.nodes == null) {
            if (n.NW != null && n.NW.viewport.intersects(rect)) {
                query2D(n.NW, rect, result);
            }
            if (n.NE != null && n.NE.viewport.intersects(rect)) {
                query2D(n.NE, rect, result);
            }
            if (n.SE != null && n.SE.viewport.intersects(rect)) {
                query2D(n.SE, rect, result);
            }
            if (n.SW != null && n.SW.viewport.intersects(rect)) {
                query2D(n.SW, rect, result);
            }
        } else {
            for (int i = 0; i < n.count; i++) {
                result.add(n.nodes[i]);
            }
            return;
        }
    }
}
